package src.dynamic_programming;

/**
 * @author starsea
 * @date 2024-08-21 14:17
 */

public class Test03 {
    public boolean isMatch(String s, String p) {
        s+=" ";
        p+=" ";
        char[] arr1=s.toCharArray();
        char[] arr2=p.toCharArray();
        int m=arr1.length;
        int n=arr2.length;
        boolean[][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int j=1;j<=n;j++)
        {
            if(arr2[j]=='*')
            {
                dp[0][j]=true;
            }
            else {
                break;
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(arr2[j]==arr1[i] || arr2[j-1]=='?')
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else if (arr2[j]=='*')
                {
                    dp[i][j]=dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
